package com.tgy.algorithm._经典题目01;

/**
 *
 * 括号有效配对是指:
 * 1)任何一个左括号都能找到和其正确配对的右括号
 * 2)任何一个右括号都能找到和其正确配对的左括号
 * 返回一个括号字符串中，最长的括号有效子串的长度
 */
public class _003_括号有效匹配对数 {

    public static int maxBracket(String content) {
        if (content == null || content.length() == 0 || content.length() == 1) {
            return 0;
        }

        int len = content.length();
        char[] chars = content.toCharArray();
        int[] nums = new int[len];
        int maxLen = 0;
        for (int i = 1; i < len; i++) {
            char curChar = chars[i];
            if (curChar == '(') {
                nums[i] = 0;
            }else {
                int index = i - nums[i - 1] - 1;
                if (index < 0) {
                    nums[i] = 0;
                }else {
                    char aChar = chars[index];
                    if (aChar == ')') {
                        nums[i] = 0;
                    }else {
                        nums[i] = 2 + nums[i  - 1] + (index - 1 >= 0 ? nums[index - 1] : 0 );
                        maxLen = Math.max(maxLen,nums[i]);
                    }
                }
            }

        }

        return maxLen;
    }

    public static void main(String[] args) {

        String content = "()(())";
        int maxLen = maxBracket(content);
        System.out.println(maxLen);
    }
}
